package  mao.leetcode.array.leetcode216;

import java.util.ArrayList;
import java.util.List;
//想不通哪里有问题。
public class Solution {
    public List<List<Integer>> res;
    public List<Integer> list;
    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        list = new ArrayList<>();
        combinationHelper(n,k,1);
        return res;
    }

    public void combinationHelper(int target,int k,int from){
        if (target < 0 || k < 0){
            return;
        }else{
            for(int i=from;i<=9;i++){
                if (i == target && k == 1){
                    list.add(i);
                    res.add(new ArrayList<>(list));
                    list.remove(list.size()-1);
                    break; //后面不可能有合适的了。剪枝。
                }else if (target > i){
                    list.add(i);
                    combinationHelper(target-i,k-1,i+1);
                    list.remove(list.size()-1);
                }
                //没有选择这个数字。
                if (target > i){
                    combinationHelper(target,k,i+1);
                }

            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.combinationSum3(3, 9);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}